package subtractiveTreatment;

import java.util.Arrays;

/**
 * @author yicixingchen
 * @version 1.0
 * Create by 2022/11/8 10:25
 */
@SuppressWarnings({"all"})
public class Main {
    public static int[] selectionSort(int[] a) {
        int min = 0;
        for (int i = 0; i <= a.length - 2; i++) {
            min = i;
            for (int j = i + 1; j <= a.length - 1; j++) {
                if (a[j] < a[min]) min = j;
            }
            int t = a[i];
            a[i] = a[min];
            a[min] = t;
        }
        return a;
    }

    public static int halfFind(int[] a, int k) {
        int i = 0;
        int r = a.length - 1;

        while (i <= r) {
            int m = (i + r) / 2;
            if (k == a[m]) return m;
            else if (k < a[m]) r = m - 1;
            else i = m + 1;
        }
        return -1;
    }

    public static void LexicographicPermute(int n) {
        int[][] result = new int[n * n][n];
        for (int i = 1; i <= n; i++) {
            result[0][i - 1] = i;
        }
        System.out.println(Arrays.toString(result[0]));
        int count = 1;
        boolean flag = true;
        while (flag){
            int i1 = 0;
            int j1 = 0;
//            result[count] = result[count - 1];
            result[count] = Arrays.copyOf(result[count - 1],n);
            flag = false;
            for (int i = 0; i < n - 1; i++) {
                if(result[count][i] < result[count][i + 1]) flag=true;
            }
            if (!flag) break;
            for (int i = 0; i < n - 1; i++) {
                if(result[count][i] < result[count][i+1]) i1 = i;
            }
            for (int i = i1 + 1; i < n; i++) {
                if (result[count][i1] < result[count][i]) j1 = i;
            }
            int t = result[count][i1];
            result[count][i1] = result[count][j1];
            result[count][j1] = t;
            for (int i = i1+1; i < n - ((n - i1) / 2) ; i++) {
                int n1 = n;
                int temp = result[count][i];
                result[count][i] = result[count][--n1];
                result[count][n1] = temp;
            }
            System.out.println(Arrays.toString(result[count]));
            count++;
        }
    }

    public static void main(String[] args) {
        int[] arr = selectionSort(new int[]{6, 3, 8, 2, 9, 1, 19, 5, 4});
        System.out.println(Arrays.toString(arr));
        System.out.println("折半查找 19 的索引为：" + halfFind(arr, 19));
        System.out.println("折半查找 7 的索引为" + halfFind(arr, 7));
        LexicographicPermute(3);
    }
}
